package tree;


import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 力扣 720. 词典中最长的单词
 * 给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
 *
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 *
 *
 *
 * */
public class LongestWord {
    /**
     * 第一种方式哈希集合
     * */
    public String getLongestWordBySet(String[] words) {
        Arrays.sort(words, (a, b) -> {
            if(a.length() != b.length()) {
                return a.length() - b.length();
            }else {
                return b.compareTo(a);
            }
        });
        Set<String> set = new HashSet<>();
        String longest = "";
        set.add("");
        for (String tmp : words) {
            if (set.contains(tmp.substring(0, tmp.length() - 1))) {
                set.add(tmp);
                longest = tmp;
            }
        }

        return longest;
    }

    /**
     * 第二种方式字典树
     * 之际梦幻联动力扣 208题
     * 我这边还是使用的之前的Trie
     * 由于search的特殊，我继承了一个子类Trie2并重写了search
     * */
    public String getLongestWordByTrie(String[] words) {
        Trie2 trie = new Trie2();
        //先把数据放入字典树
        for(String word : words) {
            trie.insert(word);
        }
        String longest = "";
        for(String word : words) {
            if(trie.search(word)) {
                //长度大于最大的替换，或者长度相同区默认排序最小的
                if(word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}
class Trie2 extends Trie {

    public Trie2() {
        super();
    }

    @Override
    public boolean search(String word) {
        //这边用不到search方法，所以直接用父类不产生影响
        Trie node = this;
        for(int i = 0;i < word.length();i ++) {
            int tmp = word.charAt(i) - 'a';
            //这边新增条件，每一个字符存的位置都应该是结尾，若不是结尾则返回false
            if(node.children[tmp] == null || !node.children[tmp].isEnd) {
                return false;
            }
            node = node.children[tmp];
        }
        //判断是否存在或者是不是结尾
        return node != null && node.isEnd;
    }
}
